#include <bits/stdc++.h>
using namespace std;

/*
1780. 判断一个数字是否可以表示成三的幂的和
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。

 

示例 1：

输入：n = 12
输出：true
解释：12 = 31 + 32
示例 2：

输入：n = 91
输出：true
解释：91 = 30 + 32 + 34
示例 3：

输入：n = 21
输出：false
 

提示：

1 <= n <= 107
*/

// 法一
// 循环 
class Solution {
public:
    bool checkPowersOfThree(int n) {
        // 直接迭代
        while (n > 0) {
            int rem = n % 3;
            if (rem == 2)   return false;
            n /= 3;
        }
        return true;
    }  
};

// 法二
// 递归
class Solution {
public:
    bool checkPowersOfThree(int n) {
        // 基准情况：n减为0时，所有位都符合要求
        if (n == 0)  return true;
        // 计算当前位的余数
        int remainder = n % 3;
        // 余数为2则不符合条件
        if (remainder == 2)  return false;
        // 递归检查更高位
        return checkPowersOfThree(n / 3);
    }  
};

// 法三
// 模拟位运算
class Solution {
public:
    // 获取n在三进制表示下的第k位（从0开始计数，最低位为第0位）
    int getTernaryBit(int n, int k) {
        int power = 1;
        for (int i = 0; i < k; ++i) {
            power *= 3;
        }
        return (n / power) % 3;
    }
    
    // 模拟三进制右移一位操作
    int ternaryRightShift(int n) {
        return n / 3;
    }
    
    bool checkPowersOfThree(int n) {
        // 修复：只需要检查最低位，不需要维护k变量
        while (n > 0) {
            // 始终检查最低位（第0位）
            int bit = getTernaryBit(n, 0);
            if (bit == 2) {
                return false;
            }
            // 右移一位，继续检查新的最低位
            n = ternaryRightShift(n);
        }
        return true;
    }
};